Electronic signature is a mechanism coming under so-called asymmetrical or public key cryptography. In this mechanism, the signatory has a secret or private key and an associated public key. He/she produces the signature of a message by applying to it a cryptographic algorithm using his/her secret key. The verifier may verify the signature by applying the same cryptographic algorithm using the corresponding public key.
The concept of group signature has also been proposed, which allows each member of a group to produce a signature such that a verifier having an adequate public key may verify that the signature was emitted by a member of the group without being able to determine the identity of the signatory. This concept is for example described in documents:
[1] “A Practical and Provably Secure Coalition-Resistant Group Signature Scheme” of G. Ateniese, J. Camenisch, M. Joye and G. Tsudik, in M. Bellare, Editor, Advance in Cryptology—CRYPTO 2000, Vol. 1880 of LNCS, p. 255-270, Springer-Verlag 2000;
[2] “Efficient Group Signature Scheme for Large Groups”, J. Camenisch, M. Stadler, in B. Kalishi, Editors, Advances in Cryptology—EUROCRYPT 97, Vol. 1294 of LNCS, p. 410-424, Springler-Verlag, 1997.
The general principle at the basis of the group signature concept is to associate with each member of the group, a distinct solution to a common difficult problem, this solution being provided by a qualified certifying authority to each new member of the group upon his/her registration. During his/her registration, the member calculates a signature private key which is specific to him/her and interacts with the certifying authority in order to obtain his/her own solution to this difficult problem. The member and the certifying authority also calculate a member certificate which is strongly related to the private key of the member and possibly to the solution of the problem known to the member. To sign a message on behalf of the group, the member encrypts his/her certificate with the public encryption key of the certifying authority, and proves that he/she knows a group member private key, a solution to the difficult problem and a member certificate associated with plain text included in the encrypted text (evidence of belonging to the group). The basis here is cryptography and more particularly evidence of knowledge in order to obtain the desired properties of the group signatures. Verification of a group signature consists of verifying the evidence of knowledge; opening the signature merely consists of decrypting the certificate.
However, in this group signature concept, a certifying authority may at any moment lift the anonymity of the signatory, i.e., determine the identity of the person of the group who has emitted a signature. Further, this type of signature is said to be “non-linkable”, i.e., it does not allow any determination whether or not two signatures were emitted by the same person without lifting the anonymity of the signature. The group signature concept is therefore not very suitable for electronic voting.
There also exists what are called list electronic signatures allowing the members of a list to produce a signature such that a verifier may recognize that the signature was produced by a member of the list, without being able to determine the identity of the member. According to the list signature concept, which is for example described in Patent Application FR 2 842 680 filed by the applicant, the time is divided into sequences marked by a sequence representative with a predefined validity period. During a sequence, each member of the list is authorized to produce the signatures from which a verifier may determine whether or not two signatures were emitted by the same member of the list, without being able to access the identity of the signatory. Thus, if a member of the list produces two signatures during the same sequence, this may be detected without being able to determine the identity of the signatory.
The list signature is thus well suited for voting or electronic surveying, because each voter may produce a list signature of his/her vote, which guarantees his/her anonymity, while the votes emitted by the same person during a same given election (sequence) may be detected. The list signature is also well suited for access tickets such as transportation tickets or cinema tickets, because the user may produce at each access to which he/she is entitled, a list signature which guarantees his/her anonymity, while the number of signatures already emitted during a given sequence may be determined, so as to authorize him/her to access the service for a certain number of times corresponding to the paid amount. However, certain list signatures are said to be “openable”, i.e. a certifying authority may determine the identity of the signatory from a signature.
More specifically, each member of a list calculates during his/her registration in the list, a private key and obtains from a certifying authority a certificate of member of the list, as well as a solution to a difficult problem. The list signature concept does not allow anonymity to be lifted; it does not include any encryption upon producing a signature. At the beginning of a given sequence, the certifying authority generates a sequence representative exclusively valid for the duration of the sequence. Upon producing a signature, a member of the list provides, as in the group signature, the evidence that he/she knows a private key, a solution to a difficult problem and a certificate of member of the list. He/she also calculates a power of the representative of the sequence for which the exponent is the private key. For a given sequence, it is possible to link two signatures produced by a same member of the list, as the representative of the sequence and the private key are set for this sequence. Therefore, the number of signatures emitted by each of the members of the list during a same sequence may thus be counted.
The major drawback of all these concepts results from the fact that they require significant calculations. Indeed, for each generated signature, it is necessary to produce pieces of evidence of knowledge which apply many modular exponentiations in practice, and are very costly in computing time, notably for generating random numbers: a chip card equipped with a cryptographic processor takes about 1 second per modular exponentiation.
A solution to this problem of computing time cost was proposed for group signatures in Patent Application FR 2 834 403 filed by the applicant. This solution which consists of applying a chip card (cryptographic processor), has the disadvantage of the group signatures, i.e., it is not possible to link the signatures emitted by a given member without lifting the anonymity of the signature.